1894D - Neutral Tonality - CodeForces Solution

//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef long double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;

const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int n, m;
int a[N], b[N];
int sufmx[N];
vii ans(N);

int find(int x)
{
    int l = 0, r = n;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (sufmx[mid] >= x)
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= m; i++)
            cin >> b[i];
        for (int i = 0; i <= n; i++)
            ans[i].clear();
        a[0] = inf;
        sufmx[n + 1] = 0;
        for (int i = n; i >= 0; i--)
            sufmx[i] = max(sufmx[i + 1], a[i]);
        for (int i = 1; i <= m; i++)
            ans[find(b[i])].push_back(b[i]);
        for (int i = 0; i <= n; i++)
            if (ans[i].size())
                sort(ans[i].begin(), ans[i].end(), greater<int>());
        for (int i = 0; i <= n; i++)
        {
            if (i)
                cout << a[i] << " ";
            for (int j = 0; j < ans[i].size(); j++)
                cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}